﻿// 0921train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 贪吃蛇是一个经典游戏，蛇的身体由若干方格连接而成，身体随蛇头移动
 蛇头触碰到食物时，蛇的长度会增加一格
 蛇头和身体的任一方格或者游戏版图边界碰撞时，游戏结束

下面让我们来完成贪吃蛇游戏的模拟。
给定一个N*M的数组arr，代表N*M个方格组成的版图，贪吃蛇每次移动一个方格。
若arr[i][j] == 'H'，表示该方格为贪吃蛇的起始位置；
若arr[i][j] == 'F'，表示该方格为食物，
若arr[i][j] == 'E'，表示该方格为空格。
贪吃蛇初始长度为1，初始移动方向为向左。
为给定一系列贪吃蛇的移动操作，返回操作后蛇的长度
如果在操作执行完之前已经游戏结束，返回游戏结束时蛇的长度
贪吃蛇移动、吃食物和碰撞处理的细节见下面图示：
图1：截取了贪吃蛇移动的一个中间状态，H表示蛇头，F表示食物，
数字为蛇身体各节的编号，蛇为向左移动，此时蛇头和食物已经相邻
图2：蛇头向左移动一格，蛇头和食物重叠，
注意此时食物的格子成为了新的蛇头，第1节身体移动到蛇头位置，
第2节身体移动到第1节身体位置，以此类推，
最后添加第4节身体到原来第3节身体的位置。
图3：蛇头继续向左移动一格，身体的各节按上述规则移动，此时蛇头已经和边界相邻，但还未碰撞。
图4：蛇头继续向左移动一格，此时蛇头已经超过边界，发生碰撞，游戏结束。
图5和图6给出一个蛇头和身体碰撞的例子，蛇为向上移动。
图5时蛇头和第7节身体相邻，但还未碰撞；
图6蛇头向上移动一格，此时蛇头和第8节身体都移动到了原来第7节身体的位置，发生碰撞，游戏结束。

输入描述
输入第一行为空格分隔的字母，代表贪吃蛇的移动操作。
字母取值为U、D、L、R和G，
U、D、L、R分别表示贪吃蛇往上、下、左、右和转向，转向时贪吃蛇不移动，
G表示贪吃蛇按当前的方向移动一格。
用例保证输入的操作正确。
第二行为空格分隔的两个数，指定N和M，为数组的行和列数。
余下N行每行是空格分隔的M个字母。字母取值为H、F和E，H表示贪吃蛇的起始位置，
F表示食物，E表示该方格为空格。
用例保证有且只有一个H，而F和E会有多个。

输出描述
输出一个数字，为蛇的长度。

示例 1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
D G G
3 3
F F F
F F H
E F E
输出
1
 */
class Solution01
{
public:
    Solution01(vector<char>&command_v, 
        vector<vector<char>>&grid,
        int row_size, int col_size
    )
    {
        //U、D、L、R
        unordered_map<char, vector<int>>DirectionMap = 
        {
			{'U',{-1,0}},
			{'D',{1,0}},
			{'L',{0,-1}},
			{'R',{0,1}}
        };

        vector<vector<bool>>checked(row_size, vector<bool>(col_size));
        int curr_r = -1, curr_c = -1;
        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
		        if (grid[r][c]=='H')
		        {
                    curr_r = r;
                    curr_c = c;
                    //标记已访问
                    checked[r][c] = true;
                    break;
		        }
	        }
        }

        
        //贪吃蛇初始长度为1，初始移动方向为向左
        int length = 1;
        char command = 'L';
        for (auto&com_char:command_v)
        {
            if (com_char=='G')
            {
                vector<int>dir = DirectionMap[command];
                curr_r += dir[0];
                curr_c += dir[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (!is_curr_r || !is_curr_c) break;
                bool is_visited = checked[curr_r][curr_c];
                //F食物 E空格
                //F表示食物，E表示该方格为空格
                bool is_growth = grid[curr_r][curr_c] == 'F';
                bool is_move = grid[curr_r][curr_c] == 'E';
                bool is_available = is_growth || is_move;

                if (!is_visited && is_available)
                {
                    if (is_growth) length++;
                    //标为已访问
                    checked[curr_r][curr_c] = true;
                    continue;
                }
                
                break;
            }
            command = com_char;
	        //for
        }


        cout << length;
	    //Solution01
    }
};


/*
题目描述
现有一组砝码，重量互不相等，分别为m1,m2,m3...mn;
每种砝码对应的数量为x1,x2,x3...xn。现在要用这些砝码去称物体的重量，问能称出多少中不同的Q重量
注：
称重重量包括0

输入描述：
输入包含多组 测试数据Q。
对于每组测试数据：
第一行：n --- 砝码种数(范围[1,10])
第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,20000])
第三行：x1 x2 x3 ... xn --- 每种砝码的数量(范围[1,6])

输出描述：
利用给定的砝码可以称出的不同的重量数

示例1
输入
2
1 2
2 1
输出
5
 */
class Solution02
{
public:
    Solution02(vector<int>&kind_v, vector<int>&count_v)
    {
        vector<int>total_v;
        int v_size = kind_v.size();
        for (int i=0; i<v_size; i++)
        {
            int count = count_v[i];
            while (count--)
            {
                total_v.push_back(kind_v[i]);
            }
        }

        int total_sum = accumulate(total_v.begin(), total_v.end(), 0);

        vector<bool>dynamic_v(total_sum + 1, false);
        dynamic_v[0] = true;
        dynamic_v[total_sum] = true;

        for (auto&curr_w:total_v)
        {
            for (int sum_w=total_sum; sum_w>=0; sum_w--)
            {
                if (sum_w - curr_w < 0) continue;

                if (dynamic_v[sum_w - curr_w])
                {
                    dynamic_v[sum_w] = dynamic_v[sum_w - curr_w];
                }
            }
        }

        int result = 0;
        for (auto item:dynamic_v)
        {
            if (item) result++;
        }

        cout << result;
	    //Solution02
    }
};

/*
 有一组区间[a0, b0], [a1, b1], ... (a, b表示起点, 终点),
 区间有可能重叠、相邻, 重叠或相邻则可以合并为更大的区间;
给定一组连接器[x1, x2, x3, ...] (x表示连接器的最大可连接长度, 即x>= gap),
可用于将分离的区间连接起来, 但两个分离区间之间只能使用1个连接器;
请编程实现使用连接器后, 最少的区间数结果。
区间数量<10000, a,b均 <=10000
连接器数量<10000; x <= 10000

输入描述
区间组: [1,10],[15,20],[18,30],[33, 40]
连接器组: [5,4,3,2]

输出描述
1

说明:
合并后: [1,10],[15,30],[33,40], 使用5, 3两个连接器连接后只剩下[1, 40]

示例 输入输出 示例仅供调试, 后台判题数据一般不包含示例
输入
[1,10],[15,20],[18,30],[33,40]
[5,4,3,2]
输出
1
说明
合并后: [1,10],[15,30],[33,40], 使用5, 3两个连接器连接后只剩下[1,40]。
 */




int main()
{
	{
        int v_size;
        cin >> v_size;
        vector<int>kind_v(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> kind_v[i];
        }
        vector<int>count_v(v_size);
        for (int i = 0; i < v_size; i++)
        {
            cin >> count_v[i];
        }

        Solution02 solu(kind_v, count_v);

        return 0;
	}
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    vector<char>command_v;
    while (oh_sstream>>token)
    {
        command_v.push_back(token[0]);
    }
    int row_size, col_size;
    cin >> row_size >> col_size;

    vector<vector<char>>grid(row_size, vector<char>(col_size));
    for (int r=0; r<row_size; r++)
    {
	    for (int c=0; c<col_size; c++)
	    {
            cin >> grid[r][c];
	    }
    }
    Solution01 solu(command_v, grid, row_size, col_size);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
